def ext_euclid(a, b):     
    if b == 0:         
        return 1, 0, a     
    else:         
        x, y, q = ext_euclid(b, a % b)
        # q = gcd(a, b) = gcd(b, a%b)         
        x, y = y, (x - (a // b) * y)
        print(x,y,q)
        return x, y, q
ext_euclid(3, 5)
